class LinkedList {
    // 初始链表长度为 0
    length = 0;

    // 初始 head 为 null，head 指向链表的第一个节点
    head = null;

    // 内部类（链表里的节点 Node）
    Node = class {
      data;
      next = null;
      constructor(data) {
        this.data = data;
      }
    };

    // ------------ 链表的常见操作 ------------ //

    // append() 往链表尾部追加数据
    append(data) {

        // 1、创建新节点
        const newNode = new this.Node(data);

        // 2、追加新节点
        if (this.length === 0) {

        // 链表长度为 0 时，即只有 head 的时候
        this.head = newNode;

        } else {
        // 链表长度大于 0 时，在最后面添加新节点
        let currentNode = this.head;

        // 当 currentNode.next 不为空时，
        // 循序依次找最后一个节点，即节点的 next 为 null 时
        while (currentNode.next !== null) {
            currentNode = currentNode.next;
        }

        // 最后一个节点的 next 指向新节点
        currentNode.next = newNode;
        }

        // 3、追加完新节点后，链表长度 + 1
        this.length++;
    }

    // 实现 toString() 方法
    toString() {
      let currentNode = this.head;
      let result = '';

      // 遍历所有的节点，拼接为字符串，直到节点为 null
      while (currentNode) {
      result += currentNode.data + ' ';
      currentNode = currentNode.next;
      }

      return result;
    }

    // 实现 insert() 方法
    // insert() 在指定位置（position）插入节点
    insert(position, data) {
      // position 新插入节点的位置
      // position = 0 表示新插入后是第一个节点
      // position = 1 表示新插入后是第二个节点，以此类推

      // 1、对 position 进行越界判断，不能小于 0 或大于链表长度
      if (position < 0 || position > this.length) return false;

      // 2、创建新节点
      const newNode = new this.Node(data);

      // 3、插入节点
      if (position === 0) { // position = 0 的情况
      // 让新节点的 next 指向 原来的第一个节点，即 head
      newNode.next = this.head;

      // head 赋值为 newNode
      this.head = newNode;
      } else { // 0 < position <= length 的情况

      // 初始化一些变量
      let currentNode = this.head; // 当前节点初始化为 head
      let previousNode = null; // head 的 上一节点为 null
      let index = 0; // head 的 index 为 0

      // 在 0 ~ position 之间遍历，不断地更新 currentNode 和 previousNode
      // 直到找到要插入的位置
      while (index++ < position) {
          previousNode = currentNode;
          currentNode = currentNode.next;
      }

      // 在当前节点和当前节点的上一节点之间插入新节点，即它们的改变指向
      newNode.next = currentNode;
      previousNode.next = newNode;
      }

      // 更新链表长度
      this.length++;
      return newNode;
    }


    // 实现 getData() 方法
    getData(position) {
        // 1、position 越界判断
        if (position < 0 || position >= this.length) return null;

        // 2、获取指定 position 节点的 data
        let currentNode = this.head;
        let index = 0;

        while (index++ < position) {
        currentNode = currentNode.next;
        }
        // 3、返回 data
        return currentNode.data;
    }

    // 实现 indexOf() 方法
    indexOf(data) {

      let currentNode = this.head;
      let index = 0;

      while (currentNode) {
      if (currentNode.data === data) {
          return index;
      }
      currentNode = currentNode.next;
      index++;
      }

      return -1;
    }


    // 实现 update() 方法
    update(position, data) {
      // 涉及到 position 都要进行越界判断
      // 1、position 越界判断
      if (position < 0 || position >= this.length) return false;

      // 2、痛过循环遍历，找到指定 position 的节点
      let currentNode = this.head;
      let index = 0;
      while (index++ < position) {
      currentNode = currentNode.next;
      }

      // 3、修改节点 data
      currentNode.data = data;

      return currentNode;
    }


    // 实现 removeAt() 方法
    removeAt(position) {
      // 1、position 越界判断
      if (position < 0 || position >= this.length) return null;

      // 2、删除指定 position 节点
      let currentNode = this.head;
      if (position === 0) {
      // position = 0 的情况
      this.head = this.head.next;

      } else {
        // position > 0 的情况
        // 通过循环遍历，找到指定 position 的节点，赋值到 currentNode

        let previousNode = null;
        let index = 0;

        while (index++ < position) {
            previousNode = currentNode;
            currentNode = currentNode.next;
        }

        // 巧妙之处，让上一节点的 next 指向到当前的节点的 next，相当于删除了当前节点。
        previousNode.next = currentNode.next;
      }

      // 3、更新链表长度 -1
      this.length--;

      return currentNode;
    }

    // 实现 remove() 方法
    remove(data) {
      this.removeAt(this.indexOf(data));
    }

    // 实现 isEmpty() 方法
    isEmpty() {
      return this.length === 0;
    }

    // 实现 size() 方法
    size() {
      return this.length;
    }

}



const linkedList = new LinkedList();
// 测试 append 方法
linkedList.append("A");
linkedList.append("B");
linkedList.append("C");
console.log(linkedList);


// 测试 toString 方法
console.log(linkedList.toString()); //--> AA BB CC

// 测试 insert 方法
linkedList.insert(0, "123");
linkedList.insert(2, "456");
console.log(linkedList.toString()); //--> 123 AA 456 BB CC


// 测试 getData 方法
console.log(linkedList.getData(0)); //--> 123
console.log(linkedList.getData(1)); //--> AA


// 测试 indexOf 方法
console.log(linkedList.indexOf("AA")); //--> 1
console.log(linkedList.indexOf("ABC")); //--> -1


// 测试 update 方法
linkedList.update(0, "12345");
console.log(linkedList.toString()); //--> 12345 AA 456 BB CC
linkedList.update(1, "54321");
console.log(linkedList.toString()); //--> 12345 54321 456 BB CC


// 测试 removeAt 方法
linkedList.removeAt(3);
console.log(linkedList.toString()); //--> 12345 54321 456 CC

// 测试 remove 方法
linkedList.remove("CC");
console.log(linkedList.toString()); //--> 12345 54321 456

// 测试 isEmpty 方法
console.log(linkedList.isEmpty()); //--> false

// 测试 size 方法
console.log(linkedList.size()); //--> 3